from collections import deque
class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.stack = deque()
        self.already_dict = {}
        self.prev_dict = {}
        self.next_dict = {}
        self.head = None
        self.last = None
        self.capacity = capacity
        self.length = 0

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.already_dict:
            return -1
        else:
            if key != self.head:
                self.next_dict[self.prev_dict[key]] = self.next_dict[key]
                if key == self.last:
                    self.last = self.prev_dict[key]
                    self.next_dict[self.last] = None
                else:
                    self.prev_dict[self.next_dict[key]] = self.prev_dict[key]
                self.next_dict[key] = self.head
                self.prev_dict[self.head] = key
                self.prev_dict[key] = None
                self.head = key
            return self.already_dict[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key not in self.already_dict:
            self.already_dict[key] = value
            if self.length < self.capacity:
                self.length += 1
                if self.length == 1:
                    self.prev_dict[key] = None
                    self.next_dict[key] = None
                    self.head = key
                    self.last = key
                else:
                    self.next_dict[key] = self.head
                    self.prev_dict[self.head] = key
                    self.prev_dict[key] = None
                    self.head = key
            else:
                self.already_dict.pop(self.last)
                if self.length == 1:
                    self.prev_dict[key] = None
                    self.next_dict[key] = None
                    self.head = key
                    self.last = key
                else:
                    self.next_dict[key] = self.head
                    self.prev_dict[self.head] = key
                    self.prev_dict[key] = None
                    self.last = self.prev_dict[self.last]
                    self.next_dict[self.last] = None
                    self.head = key
        else:
            self.already_dict[key] = value
            if key != self.head:
                self.next_dict[self.prev_dict[key]] = self.next_dict[key]
                if key == self.last:
                    self.last = self.prev_dict[key]
                    self.next_dict[self.last] = None
                else:
                    self.prev_dict[self.next_dict[key]] = self.prev_dict[key]
                self.next_dict[key] = self.head
                self.prev_dict[self.head] = key
                self.prev_dict[key] = None
                self.head = key


data = LRUCache(2)
data.put(1, 1)
data.put(2, 2)
print(data.get(1))
data.put(3, 3)
print(data.get(2))
data.put(4, 4)
print(data.get(1))
print(data.get(3))
print(data.get(4))